package SortSummary;

/*
*   快速排序
*       排序规则：
*           快速排序与荷兰国旗问题相关。荷兰问题是指选一个数，比这个数小的在这个数前面，比这个数大的在这个数后面，等于这个数的在中间。
*           荷兰国旗问题并不能让数据有序，但是将数组partition后在分成2个数组，对这些数组在进行partition求解，每一次partition都可以排好一部分数据，最后就会做到整体有序。(partition就是荷兰国旗问题)
*       根据荷兰国旗问题的不同要求，快排在实现执行上也有不同的效率
*
*       version1.0:
*           问题描述：
*               给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
*           实现规则：
*               1.对数组整体做partition后返回一个值，这个值标志着已经排好序的数据的下标
*               2.根据排好序的数据将数组未排好序的部分划分为2份，继续partition
*               3.继续步骤1、2，直到遍历到边界（left>right）
*           时间复杂度：O(N^2)
*           空间复杂度：O(1)
*
*       version2.0:
*            问题描述：
*               给定一个数组arr,和一个数num,请把小于num的数放在数组的左边，等于num的数放中间，大于num的数放在数组的右边。
*            实现规则：
*                  1.对数组整体做partition后返回一个数组，这个数组中放的是已经排好序的数据区域下标
*                  2.根据排好序的数据将数组未排好序的部分划分为2份，继续partition
*                  3.继续步骤1、2，直到遍历到边界（left>=right）
*            时间复杂度：O(N^2)
*            空间复杂度：O(1)
*
*       version3.0
*           对于version1.0和2.0来说，每次找的num都是最右边的数，所以对于这种情况：1，2，3，4，5，6，7或者这种情况：7，6，5，4，3，2，1来说，每次partiton都只有一侧区域，没有另一侧区域，所以最坏时间复杂度为O(n^2)
*           针对这种情况，我们可以随机选择一个数作为num，这样时间复杂度可以降到O(nlogN)
*           时间复杂度：O(nlogN)
*           空间复杂度：O(1)
* */

class QuickSort {
    static void quickSort(int[] nums,int left,int right){
        if(left >= right){
            return;
        }

        //version1.0
        int mid = partitionVersion1(nums,left,right);
        quickSort(nums,left,mid-1);
        quickSort(nums,mid+1,right);

        //version2.0
        /*int[] mid = partitionVersion2(nums,left,right);
        quickSort(nums,left,mid[0]-1);
        quickSort(nums,mid[1]+1,right);*/

        //version3.0
        /*int[] mid = partitionVersion3(nums,left,right);
        quickSort(nums,left,mid[0]-1);
        quickSort(nums,mid[1]+1,right);*/
    }

    /*
    *   荷兰国旗问题1.0
    *       步骤：
    *           1.设立小于等于区的下标，初始值为左边界-1
    *           2.遍历区间数组，如果数据小于等于num，将数据和小于等于区后面的数据交换，小于等于区扩容一位
    *           3.遍历完毕后将num和小于等于区的后面数据交换，返回num最后的下标
    *           注：num是partition区间的最后一位数
    * */
    private static int partitionVersion1(int[] nums,int left,int right){
        int p = left-1;//小于等于区下标，初始值为left-1说明小于等于区此时无数据
        int pl = left;
        int num = nums[right];
        while(pl<=right){
            if(nums[pl]<=num){
                swapArray(nums,pl,++p);
            }
            pl++;
        }
        return p;
    }

    /*
     *   荷兰国旗问题2.0
     *       步骤：
     *           1.设立小于区的下标，初始值为左边界-1；设立大于区的下标，初始值为右边界+1。
     *           2.遍历区间数组。
     *                  如果数据小于num，将数据和小于区后面的数据交换，小于区扩容一位(小于区边界下标+1)
     *                  如果数据等于num，遍历下一个数据
     *                  如果数据大于num，将数据和大于区前面的数据交换，大于区扩容一位(大于区边界下标-1)，继续遍历该位置上的数
     *           3.等遍历到大于区停止遍历，将num放到等于区，返回等于区的范围下标
     * */
    private static int[] partitionVersion2(int[] nums, int left, int right){
        int p1 = left-1;//小于区下标
        int p2 = right;//大于区下标
        int p = left;//遍历数组的下标
        int num = nums[right];

        //选择随机num
        /*int index = (int)(Math.random()*(right-left+1)+left);
        swapArray(nums,index,right);
        int num = nums[right];
        System.out.println(num);*/
        while(p<p2){
            if(nums[p]<num){
                swapArray(nums,p++,++p1);
            }else if(nums[p]==num){
                p++;
            }else if(nums[p]>num){
                swapArray(nums,p,--p2);
            }
        }
        swapArray(nums,p1+1,right);
        return new int[]{p1+1,p-1};
    }

    /*
    *   version3.0
    *       在2.0上优化了num的选择，不再是固定选择最右边的数，而是随机选择数组中的一个数
    * */
    private static int[] partitionVersion3(int[] nums, int left, int right){
        int p1 = left-1;//小于区下标
        int p2 = right;//大于区下标
        int p = left;//遍历数组的下标

        //选择随机num
        int index = (int)(Math.random()*(right-left+1)+left);
        swapArray(nums,index,right);
        int num = nums[right];

        while(p<p2){
            if(nums[p]<num){
                swapArray(nums,p++,++p1);
            }else if(nums[p]==num){
                p++;
            }else if(nums[p]>num){
                swapArray(nums,p,--p2);
            }
        }
        swapArray(nums,p1+1,right);
        return new int[]{p1+1,p-1};
    }

    //交换数组中下标是i,j的数据
    private static void swapArray(int[] nums,int i,int j){
        int n = nums[i];
        nums[i] = nums[j];
        nums[j] = n;
    }
}
